﻿#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <iostream>
using namespace std;

// 枚举表示颜色
enum Colour
{
	RED,
	BLACK
};



template<class K, class V>
struct RBTreeNode
{

	pair<K, V> _kv;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	Colour _col;


	RBTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
	{}
};


template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			Node* newnode = new Node(kv);
			newnode->_col = BLACK;
			_root = newnode;
			return true;
		}

		Node* father = nullptr;
		Node* cur = _root;
		while (cur)
		{
			father = cur;
			if (kv.first < cur->_kv.first)
			{
				cur = cur->_left;
			}
			else if (kv.first > cur->_kv.first)
			{
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		
		cur = new Node(kv);
		cur->_col = RED;
		if (cur->_kv.first < father->_kv.first)
		{
			father->_left = cur;
			cur->_parent = father;
		}
		else
		{
			father->_right = cur;
			cur->_parent = father;
		}


		//更新红黑
		while (father && father->_col == RED)
		{
		
			Node* grandfather = father->_parent;
		
			
			if (father == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				//情况1 变色
				if (uncle && uncle->_col == RED)
				{
					grandfather->_col = RED;
					uncle->_col = father->_col = BLACK;

					cur = grandfather;
					father = cur->_parent;
				}
				else if(uncle == nullptr || uncle->_col == BLACK)//情况2：旋转
				{
					//单旋
					if (cur == father->_left)
					{
						//右旋;
						RotateR(grandfather);
						father->_col = BLACK;
						grandfather->_col = RED;
					}
					else if (cur == father->_right)//双旋
					{
						//左右双旋;
						RotateLR(grandfather);
						grandfather->_col = RED;
						cur->_col = BLACK;
					
					}

					break;
				}
				

			}
			else if (father == grandfather->_right)
			{
				Node* uncle = grandfather->_left;
				//情况1 变色
				if (uncle && uncle->_col == RED)
				{
					grandfather->_col = RED;
					uncle->_col = father->_col = BLACK;

					cur = grandfather;
					father = cur->_parent;
				}
				else if (uncle == nullptr || uncle->_col == BLACK)//情况2：旋转
				{
					//单旋
					if (cur == father->_right)
					{
						//左旋;
						RotateL(grandfather);
						father->_col = BLACK;
						grandfather->_col = RED;
					}
					else if(cur == father->_left)
					{
						RotateRL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;

				}
			}

		}
		_root->_col = BLACK;
		return true;
	}


	// 右单旋

	void RotateR(Node* parent)
	{
		Node* father = parent;
		Node* sonL = father->_left;
		// 1. 先把 sonL 挪到 father 的位置
		sonL->_parent = father->_parent;
		if (father->_parent)
		{
			if (father == father->_parent->_left)
			{

				father->_parent->_left = sonL;
			}
			else
			{
				father->_parent->_right = sonL;

			}
		}
		else
		{
			_root = sonL;
		}

		// 2. 调整 father
		father->_parent = sonL;
		father->_left = sonL->_right;

		if (sonL->_right)
			sonL->_right->_parent = father;

		sonL->_right = father;

	}

	// 左单旋
	void RotateL(Node* parent)
	{
		Node* father = parent;
		Node* sonR = father->_right;

		sonR->_parent = father->_parent;
		if (father->_parent)
		{
			if (father == father->_parent->_left)
			{
				father->_parent->_left = sonR;
			}
			else
			{
				father->_parent->_right = sonR;

			}
		}
		else
		{
			_root= sonR;
		}

		father->_parent = sonR;
		father->_right = sonR->_left;

		if (sonR->_left)
			sonR->_left->_parent = father;

		sonR->_left = father;


	}
	// 右左双旋
	void RotateRL(Node* parent)
	{

		
		Node* sonR = parent->_right;
		Node* sonRL = sonR->_left;

		RotateR(sonR);
		RotateL(parent);

	
	}
	// 左右双旋
	void RotateLR(Node* parent)
	{


		Node* sonL = parent->_left;
		Node* sonLR = sonL->_right;

		RotateL(sonL);
		RotateR(parent);
		
	}
	void InOrder()
	{
		_InOrder(_root);
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}


		_InOrder(root->_left);
		cout << root->_kv.first << " ";
		_InOrder(root->_right);
	}


	// 前序递归遍历
	bool Check(Node* root, int blackNum, const int refNum)
	{
		if (root == nullptr)
		{
			// 前序遍历走到空时，意味着一条路径走完了
			//cout << blackNum << endl;
			if (refNum != blackNum)
			{
				cout << "存在黑色结点的数量不相等的路径" << endl;
				return false;
			}
			return true;
		}


		// 检查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲就方便多了
		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
		{
			cout << root->_kv.first << "存在连续的红色结点" << endl;
			return false;
		}


		if (root->_col == BLACK)
		{
			blackNum++;
		}


		return Check(root->_left, blackNum, refNum)
			&& Check(root->_right, blackNum, refNum);
	}


	bool IsBalanceTree()
	{
		if (_root == nullptr)
			return true;


		if (_root->_col == RED)
			return false;


		// 参考值
		int refNum = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				++refNum;
			}
			cur = cur->_left;
		}


		return Check(_root, 0, refNum);
	}


private:
	Node* _root = nullptr;
};